#include<stdlib.h>
#include<stdio.h>

#define SIZE 100

int **merge_sort(int **arr, unsigned int size, unsigned char asend_flag)
{
	int **part1, **part2;
	int **ret;
	int i=0,j=0,k=0;
	
	if(size == 1)
	{
		ret = (int **) malloc(sizeof(int *));
		ret[0] = arr[0];
		return ret;
	}
	if(size == 2)
	{
		ret =(int **) malloc(sizeof(int *) * size);
		if(((*arr[0]>*arr[1])&&asend_flag)||((*arr[0]<*arr[1])&& !asend_flag))
		{
			ret[0] = arr[1];
			ret[1] = arr[0];
			return ret;
		}
		ret[0] = arr[0];
		ret[1] = arr[1];
		return ret;
	}
	part1 = merge_sort(arr, size/2, asend_flag);
	part2 = merge_sort(arr + size/2, size-size/2, asend_flag);

	ret = (int **) malloc(sizeof(int *) * size);
	for(;i<size && j<size/2 && k<(size - size/2);i++)
	{
		ret[i] = malloc(sizeof(int *));
		if(((*part1[j]<*part2[k])&&asend_flag)||((*part1[j]>*part2[k])&& !asend_flag))
		{
			ret[i] = part1[j];
			j++;
		}
		else if(((*part2[k]<*part1[j])&&asend_flag)||((*part2[k]>*part1[j])&& !asend_flag))
		{
			ret[i] = part2[k];
			k++;
		}
		else
		{
			ret[i] = part1[j];
			ret[i+1] = part2[k];
			i++;
			j++;
			k++;
		}
	}
	
	for(;j<size/2;j++,i++)
	{
		ret[i] = malloc(sizeof(int *));
		ret[i] = part1[j];
	}
	for(;k<(size - size/2);k++,i++)
	{
		ret[i] = malloc(sizeof(int *));
		ret[i] = part2[k];
	}
	return ret;

}

int **pointer_sort(int *arr, unsigned int size, unsigned char asend_flag)
{
	int **ret =(int **)malloc(sizeof(int *) * size);
	for(int i=0;i<size;i++)
		ret[i] = &arr[i];
	return merge_sort(ret, size, asend_flag);


}

void **printPointers(int **arr, int size)
{
	int **p;
	for(p=arr;p - arr<size;p++)
		printf("%d\t", **p);
}

int main()
{
	unsigned int size, i;
	int arr[SIZE];
	int **pointers;
	int ascend_flag;
	printf("Please enter the number of items:\n");
	scanf("%u", &size);
	for(i=0; i<size; i++)
	    scanf("%d", &arr[i]);
	scanf("%d", &ascend_flag);
 
	pointers = pointer_sort(arr, size, (char)ascend_flag);
	printf("The sorted array:\n");//Print the sorted array
	printPointers(pointers, size);
	free(pointers);
	return 0;

}
